A
弱智题,讨论 的奇偶性即可。
Code
#include <cstdio>
int T, a, b;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &a, &b);
a--, b--;
if (a % 2 == b % 2) puts("Tonya");
else puts("Burenka");
}
}
B
弱智题,讨论 模 的余数即可。
Code
#include <cstdio>
int T, n, k;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
if (k % 2) {
puts("YES");
for (int i = 1; i <= n; i += 2) printf("%d %d\n", i, i + 1);
}
else if (k % 4 == 0) puts("NO");
else if (k % 4 == 2) {
puts("YES");
for (int i = 1; i <= n; i += 4) {
printf("%d %d\n", i + 1, i);
if (i != n - 1) printf("%d %d\n", i + 2, i + 3);
}
}
}
}
C
注意到最多进行 轮比赛实力为 的人就会被换到第一位,往后只会有这个人获胜。
我们对询问离线,按 排序,先预处理 轮以内的胜负情况。对于超过 轮的比赛,对询问的人实力是否为 分类讨论即可。
时间复杂度 。
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
struct Query {
int x, k, id;
Query() {}
Query(int x, int k, int id) : x(x), k(k), id(id) {}
} q[N];
bool operator <(const Query &a, const Query &b) {
return a.k < b.k;
}
int n, m, T, ans[N], a[N], win[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].x, &q[i].k);
q[i].id = i;
}
sort(q + 1, q + m + 1);
memset(ans, 0, sizeof(ans));
memset(win, 0, sizeof(win));
int cnt = 1, p = 1;
for (int i = 2; i <= n; i++) {
if (a[i] > a[p]) win[i]++, p = i;
else win[p]++;
while (q[cnt].k == i - 1 && cnt <= m) {
ans[q[cnt].id] = win[q[cnt].x];
cnt++;
}
}
for (int i = cnt; i <= m; i++) {
if (q[i].x != p) ans[q[i].id] = win[q[i].x];
else ans[q[i].id] = win[p] + q[i].k - n + 1;
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
}
D1 & D2
观察到区间操作的代价为 意味着选择一个数和两个相邻数操作的代价是一样的,所以我们可以把操作变为以下两个:
-
选择下标 和整数 并将 ,代价为 。
-
选择下标 和整数 并将 ,代价为 。
所以我们考虑把原序列划分成极小的异或和为 的连续段,对于每一段 我们可以用 的代价把这一段变为 。
这样操作与让 的每一个 异或上自己相比是不劣的 ,所以容易证明划分为极小段减少的代价最多。
划分极小段这件事情可以通过把前缀异或和插入到 中实现,时间复杂度 。
Code
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int T, n, sum, ans, a[N];
map<int, int> mp;
void solve() {
scanf("%d", &n);
mp.clear();
mp[0] = 1, sum = 0, ans = n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
sum ^= a[i];
if (mp.find(sum) != mp.end()) {
ans--;
mp.clear();
sum = 0;
mp[0] = 1;
}
else mp[sum] = 1;
}
printf("%d\n", ans);
}
int main() {
scanf("%d", &T);
while (T--) solve();
}
E
待补。
F
待补。